//括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。 
//
// 说明：解集不能包含重复的子集。 
//
// 例如，给出 n = 3，生成结果为： 
//
// 
//[
//  "((()))",
//  "(()())",
//  "(())()",
//  "()(())",
//  "()()()"
//]
// 
//
// Related Topics 字符串 动态规划 回溯 👍 135 👎 0


import java.nio.channels.WritableByteChannel;
import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(res, n, n, "");
        return res;
    }

    private void dfs(List<String> res, int left, int right, String cur) {
        if(left == 0 && right == 0){
            res.add(cur);
            return;
        }
        if(left<0 || right < left){
            return;
        }
        dfs(res, left-1, right, cur+"(");
        dfs(res, left, right-1, cur+")");
    }
}
//leetcode submit region end(Prohibit modification and deletion)
